{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check Array Formation Through Concatenation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canFormArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #能否连接形成数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> ，数组中的每个整数 <strong>互不相同</strong> 。另有一个由整数数组构成的数组 <code>pieces</code>，其中的整数也 <strong>互不相同</strong> 。请你以 <strong>任意顺序</strong> 连接 <code>pieces</code> 中的数组以形成 <code>arr</code> 。但是，<strong>不允许</strong> 对每个数组 <code>pieces[i]</code> 中的整数重新排序。</p>\n",
    "\n",
    "<p>如果可以连接<em> </em><code>pieces</code> 中的数组形成 <code>arr</code> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [15,88], pieces = [[88],[15]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>依次连接 <code>[15]</code> 和 <code>[88]</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [49,18,16], pieces = [[16,18,49]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>即便数字相符，也不能重新排列 pieces[0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [91,4,64,78], pieces = [[78],[4,64],[91]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>依次连接 <code>[91]</code>、<code>[4,64]</code> 和 <code>[78]</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pieces.length &lt;= arr.length &lt;= 100</code></li>\n",
    "\t<li><code>sum(pieces[i].length) == arr.length</code></li>\n",
    "\t<li><code>1 &lt;= pieces[i].length &lt;= arr.length</code></li>\n",
    "\t<li><code>1 &lt;= arr[i], pieces[i][j] &lt;= 100</code></li>\n",
    "\t<li><code>arr</code> 中的整数 <strong>互不相同</strong></li>\n",
    "\t<li><code>pieces</code> 中的整数 <strong>互不相同</strong>（也就是说，如果将 <code>pieces</code> 扁平化成一维数组，数组中的所有整数互不相同）</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-array-formation-through-concatenation](https://leetcode.cn/problems/check-array-formation-through-concatenation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-array-formation-through-concatenation](https://leetcode.cn/problems/check-array-formation-through-concatenation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[15,88]\\n[[88],[15]]', '[49,18,16]\\n[[16,18,49]]', '[91,4,64,78]\\n[[78],[4,64],[91]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]: p for p in pieces}\n",
    "\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if sub := d.get(arr[i]):\n",
    "                if sub != arr[i:i+len(sub)]:\n",
    "                    return False\n",
    "                i += len(sub)\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]:p for p in pieces}\n",
    "        i = 0\n",
    "        n = len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in d:return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i:i+len(p)] != p:return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]:i for i,p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i<len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(p)]!=p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index={p[0]:i for i,p in enumerate(pieces)}\n",
    "        i=0\n",
    "        while i<len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p=pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(p)]!=p:\n",
    "                return False\n",
    "            i+=len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        dictionary = dict(zip([key[0] for key in pieces], range(len(pieces))))\n",
    "        index = 0\n",
    "        while index < len(arr):\n",
    "            if arr[index] in dictionary.keys():\n",
    "                if pieces[dictionary[arr[index]]] == arr[index : index + len(pieces[dictionary[arr[index]]])]:\n",
    "                    index += len(pieces[dictionary[arr[index]]])\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        s = \"-\"\n",
    "        for i in arr:\n",
    "            s = s+str(i)+\"-\"\n",
    "        for p in pieces:\n",
    "            t = \"\"\n",
    "            for c in p:\n",
    "                t = t+str(c)+\"-\"\n",
    "            if t not in s:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]: p for p in pieces}\n",
    "        i, n = 0, len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in d:\n",
    "                return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        n = len(arr)\n",
    "        def fun(nums: list[int]):\n",
    "            index = 0\n",
    "            while index < n and arr[index] != nums[0]:\n",
    "                index += 1\n",
    "            if index >= n:\n",
    "                return False\n",
    "            if len(nums) == 1:\n",
    "                return True\n",
    "            for item in nums:\n",
    "                if index >= n or item != arr[index]:\n",
    "                    return False\n",
    "                index += 1\n",
    "            return True\n",
    "        for item in pieces:\n",
    "            if fun(item) == False:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]: p for p in pieces}\n",
    "\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if sub := d.get(arr[i]):\n",
    "                if sub != arr[i:i+len(sub)]:\n",
    "                    return False\n",
    "                i += len(sub)\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            k = 0\n",
    "            while k < len(pieces) and pieces[k][0] != arr[i]:\n",
    "                k += 1\n",
    "            if k == len(pieces):\n",
    "                return False\n",
    "            j = 0\n",
    "            while j < len(pieces[k]) and arr[i] == pieces[k][j]:\n",
    "                i, j = i + 1, j + 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]: p for p in pieces}\n",
    "        i, n = 0, len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in d:\n",
    "                return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        if len(arr)<=1:\n",
    "            return arr==pieces[0]\n",
    "        ls = [-1]*101\n",
    "        for i in range(len(arr)):\n",
    "            ls[arr[i]] = i\n",
    "        for p in pieces:\n",
    "            idx = -1\n",
    "            for i in p:\n",
    "                if ls[i]==-1 or (idx!=-1 and idx!=ls[i]-1):\n",
    "                    return False\n",
    "                idx = ls[i]\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = 0\n",
    "        while index < len(arr):\n",
    "            sign = True\n",
    "            for piece in pieces:\n",
    "                if arr[index] == piece[0]:\n",
    "                    sign = not sign\n",
    "                    for i in piece:\n",
    "                        if i == arr[index]:\n",
    "                            index += 1\n",
    "                        else:\n",
    "                            return False\n",
    "                    break\n",
    "            if sign:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        dic = {pi[0]:pi for pi in pieces}\n",
    "        return arr == sum([dic[ar] for ar in arr if ar in dic], [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {p[0]: p for p in pieces}\n",
    "        i, n = 0, len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in d:\n",
    "                return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        x=[]\n",
    "        for i in arr:\n",
    "            for j in pieces:\n",
    "                if i==j[0]:\n",
    "                    x+=j\n",
    "        return x==arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index={p[0]:i for i,p in enumerate(pieces)}\n",
    "        i=0\n",
    "        while i<len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            cur=pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(cur)]!=cur:\n",
    "                return False\n",
    "            i+=len(cur)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        def check(v):\n",
    "            for i, x in enumerate(arr):\n",
    "                if x == v[0]:\n",
    "                    for j in range(len(v)):\n",
    "                        if i + j == len(arr) or arr[i + j] != v[j]:\n",
    "                            return False\n",
    "            return p[0] in arr\n",
    "        for p in pieces:\n",
    "            if not check(p):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        try:\n",
    "            for l in pieces:\n",
    "                start = arr.index(l[0])\n",
    "                if arr[start:start + len(l)] != l:\n",
    "                    return False\n",
    "            return True\n",
    "        except ValueError:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        dic = {p[0]: len(p) for p in pieces}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in dic or arr[i: i + dic[arr[i]]] not in pieces:\n",
    "                return False\n",
    "            else:\n",
    "                i = i + dic[arr[i]]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {}\n",
    "        for p in pieces:\n",
    "            d[p[0]] = p\n",
    "       \n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if sub := d.get(arr[i]):\n",
    "                for e in sub:\n",
    "                    if e != arr[i]:\n",
    "                        return False\n",
    "                    i += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for i in pieces:\n",
    "            if i[0] not in arr:\n",
    "                return False\n",
    "            i.insert(0,arr.index(i[0]))\n",
    "        pieces.sort()\n",
    "        ans=[]\n",
    "        for i in pieces:\n",
    "            ans+=i[1:]\n",
    "        return ans==arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {}\n",
    "        for p in pieces:\n",
    "            d[p[0]] = p\n",
    "       \n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if sub := d.get(arr[i]):\n",
    "                if sub != arr[i:i+len(sub)]:\n",
    "                    return False\n",
    "                i += len(sub)\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {pieces[i][0]: pieces[i] for i in range(len(pieces))}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in d:\n",
    "                return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i:i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        #dic = dict(enumerate(arr))\n",
    "        dic = {}\n",
    "        for i,ss in enumerate(arr):\n",
    "            dic[ss] = i\n",
    "        for ss in pieces:\n",
    "            if len(ss)>0:\n",
    "                i = 1\n",
    "                if ss[0] not in dic:\n",
    "                    return False\n",
    "                while i <len(ss):\n",
    "                    if ss[i] not in dic:\n",
    "                        return False\n",
    "                    if dic[ss[i]]-dic[ss[i-1]]!=1:\n",
    "                        return False\n",
    "                    i+=1\n",
    "        return True\n",
    "                    \n",
    "                    \n",
    "            \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:                \n",
    "        flag=True\n",
    "        sarr=set(arr)\n",
    "        for i in pieces:\n",
    "            if len(i)==1:\n",
    "                if i[0] not in arr:\n",
    "                    flag=False\n",
    "            if len(i)>1:\n",
    "                for j in range(0,len(i)):\n",
    "                    if i[j] not in sarr:\n",
    "                        flag=False\n",
    "                        break     \n",
    "                    else:\n",
    "                        if j>=1 and (arr.index(i[j]) < arr.index(i[j-1]) or arr.index(i[j]) - arr.index(i[j-1])>1):\n",
    "                            flag=False\n",
    "                            break\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        s=set(arr)\n",
    "        t=set()\n",
    "        for piece in pieces:\n",
    "            for i in range(len(piece)):\n",
    "                t.add(piece[i])\n",
    "        if s!=t:\n",
    "            return False\n",
    "        index=dict()\n",
    "        for i in range(len(arr)):\n",
    "            index[arr[i]]=i\n",
    "        for piece in pieces:\n",
    "            if len(piece)>=2:\n",
    "                if index[piece[0]]+len(piece)-1>len(arr)-1:\n",
    "                    return False\n",
    "                for j in range(len(piece)):\n",
    "                    if piece[j]!=arr[index[piece[0]]+j]:\n",
    "                        return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        n = len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index={p[0]:i for i,p in enumerate(pieces)}\n",
    "        i=0\n",
    "        while i<len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p=pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(p)]!=p:\n",
    "                return False\n",
    "            i+=len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        dic = {}\n",
    "        for i,v in enumerate(arr):\n",
    "            dic[v] = i\n",
    "        for piece in pieces:\n",
    "            if piece[0] not in dic:\n",
    "                return False\n",
    "            else:\n",
    "                tmp = dic[piece[0]]+1\n",
    "                for j in range(1,len(piece)):\n",
    "                    if tmp >= len(arr) or piece[j] != arr[tmp]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        tmp += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        # arr1 = '#'+'##'.join(list(map(str,arr)))+'#'\n",
    "        # pieces1 = []\n",
    "        # for i in pieces:\n",
    "        #     pieces1.append('#'+'##'.join(list(map(str,i)))+\"#\")\n",
    "        # pieces1 = sorted(pieces1,key=len,reverse=True)\n",
    "        # for i in pieces1:\n",
    "        #     if i in arr1:\n",
    "        #         arr1=arr1.replace(i,'',1)\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # if arr1 !='':\n",
    "        #     return False\n",
    "        # return True\n",
    "\n",
    "        d = {p[0]: p for p in pieces}\n",
    "        i, n = 0, len(arr)\n",
    "        while i < n:\n",
    "            if arr[i] not in d:\n",
    "                return False\n",
    "            p = d[arr[i]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for p in pieces:\n",
    "            l = len(p)\n",
    "            for i in range(len(arr) - l + 1):\n",
    "                if arr[i : i + l] == p:\n",
    "                    arr[i : i + l] = [0] * l \n",
    "                    break\n",
    "            else: return False\n",
    "        return set(arr) == {0}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        d = {}\n",
    "        if set(arr) != set(c for i in pieces for c in i):\n",
    "            return False\n",
    "        for i in pieces:\n",
    "            d[i[0]] = i\n",
    "        j = 0\n",
    "        while j < len(arr):\n",
    "            a = arr[j]\n",
    "            if d.get(arr[j]):\n",
    "                b = 0\n",
    "                while b < len(d[a]):\n",
    "                    if d[a][b] != arr[j]:\n",
    "                        return False\n",
    "                    b += 1\n",
    "                    j += 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]:i for i, p in enumerate(pieces)}\n",
    "        i=0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        dict = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in dict:\n",
    "                return False\n",
    "            p = pieces[dict[arr[i]]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        hash_map = {}\n",
    "        for piece in pieces:\n",
    "            hash_map[piece[0]] = piece\n",
    "        \n",
    "        index = 0 \n",
    "        while index < len(arr):\n",
    "            if arr[index] in hash_map:\n",
    "                l = len(hash_map[arr[index]])\n",
    "                if arr[index:index+l] == hash_map[arr[index]]:\n",
    "                    index += l \n",
    "                else:\n",
    "                    return False \n",
    "            else:\n",
    "                return False \n",
    "        return True\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for piece in pieces:\n",
    "            if piece[0] in arr:\n",
    "                j = arr.index(piece[0])\n",
    "                for i in range(1, len(piece)):\n",
    "                    if len(arr) <= j + i or piece[i] != arr[j + i]:\n",
    "                        return False\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for i in pieces:\n",
    "            if i[0] not in arr:\n",
    "                return False #如果pieces中有arr中没有的元素，那么肯定组成不了啦\n",
    "            i.insert(0,arr.index(i[0]))\n",
    "        pieces.sort() #排序\n",
    "        ans = [] \n",
    "        for i in pieces:\n",
    "            ans += i[1:] # 去掉头，拼接起来\n",
    "        return ans == arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:                \n",
    "        flag=True\n",
    "        for i in pieces:\n",
    "            if len(i)==1:\n",
    "                if i[0] not in arr:\n",
    "                    flag=False\n",
    "            if len(i)>1:\n",
    "                for j in range(0,len(i)):\n",
    "                    if i[j] not in arr:\n",
    "                        flag=False\n",
    "                        break     \n",
    "                    else:\n",
    "                        if j>=1 and (arr.index(i[j]) < arr.index(i[j-1]) or arr.index(i[j]) - arr.index(i[j-1])>1):\n",
    "                            flag=False\n",
    "                            break\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i : i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for i in pieces:\n",
    "            if len(i)==1:\n",
    "                for j in range(len(arr)):\n",
    "                    if arr[j]==i[0]:\n",
    "                        arr[j]=0\n",
    "                        break\n",
    "            else:\n",
    "                try:\n",
    "                    a = arr.index(i[0])\n",
    "                    b = arr.index(i[-1])\n",
    "                    if arr[a:b+1]==i:\n",
    "                        arr[a:b+1]=[0]*(b+1-a)\n",
    "                    else:\n",
    "                        return False\n",
    "                except:\n",
    "                    return False\n",
    "        if arr==[0]*len(arr):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:                \n",
    "        flag=True\n",
    "        sarr=set(arr)\n",
    "        for i in pieces:\n",
    "            if len(i)==1:\n",
    "                if i[0] not in arr:\n",
    "                    flag=False\n",
    "            if len(i)>1:\n",
    "                for j in range(len(i)):\n",
    "                    if i[j] not in sarr:\n",
    "                        flag=False\n",
    "                        break     \n",
    "                    else:\n",
    "                        if j>=1 and (arr.index(i[j]) < arr.index(i[j-1]) or arr.index(i[j]) - arr.index(i[j-1])>1):\n",
    "                            flag=False\n",
    "                            break\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        # 就是要求piece中的每个数组的顺序和arr中的一致\n",
    "        index = {}\n",
    "        for i, p in enumerate(pieces):\n",
    "            index[p[0]] = i\n",
    "        \n",
    "        j = 0\n",
    "        while j < len(arr):\n",
    "            # 按顺序排列的，肯定应该在\n",
    "            if arr[j] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[j]]]\n",
    "            # 计算相同长度数组是否一样\n",
    "            if arr[j: j + len(p)] != p:\n",
    "                return False\n",
    "            j += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "         for p in pieces:\n",
    "            l = len(p)\n",
    "            for i in range(len(arr) - l + 1):\n",
    "                if arr[i : i + l] == p:\n",
    "                    arr[i : i + l] = [0] * l \n",
    "                    break\n",
    "            else: return False\n",
    "         return set(arr) == {0}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            p = pieces[index[arr[i]]]\n",
    "            if arr[i: i + len(p)] != p:\n",
    "                return False\n",
    "            i += len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "\n",
    "\n",
    "        date_list = []\n",
    "        arr_len = len(arr)\n",
    "        pieces_len = len(pieces)\n",
    "        for i in range(0, arr_len):\n",
    "            for j in range(0, pieces_len):\n",
    "                if arr[i] in pieces[j] and not pieces[j] in date_list:\n",
    "                    date_list += [pieces[j]]\n",
    "\n",
    "        \n",
    "\n",
    "        sum = []\n",
    "        for date in date_list:\n",
    "            sum += date\n",
    "        try:\n",
    "            for i in range(0, arr_len):\n",
    "                if arr[i] != sum[i]:\n",
    "                    return False\n",
    "        except:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        try:\n",
    "            for l in pieces:\n",
    "                start = arr.index(l[0])\n",
    "                if arr[start:start + len(l)] != l:\n",
    "                    return False\n",
    "            return True\n",
    "        except ValueError:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        for i in pieces:\n",
    "            if len(i)==1:\n",
    "                for j in range(len(arr)):\n",
    "                    if arr[j]==i[0]:\n",
    "                        arr[j]=0\n",
    "                        break\n",
    "            else:\n",
    "                try:\n",
    "                    a = arr.index(i[0])\n",
    "                    b = arr.index(i[-1])\n",
    "                    if arr[a:b+1]==i:\n",
    "                        arr[a:b+1]=[0]*(b+1-a)\n",
    "                    else:\n",
    "                        return False\n",
    "                except:\n",
    "                    return False\n",
    "        for i in arr:\n",
    "            if i!=0:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        # dic = {}\n",
    "        # for piece in pieces:\n",
    "        #     dic[piece[0]] = piece\n",
    "        # print(dic)\n",
    "        index = {p[0]: i for i, p in enumerate(pieces)}\n",
    "        print(index)\n",
    "        i=0\n",
    "        while i <len(arr):\n",
    "            print(arr[i])\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            idx=index[arr[i]]\n",
    "            # print(pieces[idx])\n",
    "            p=pieces[idx]\n",
    "\n",
    "            print()\n",
    "            if arr[i:i + len(p)] !=p:\n",
    "                return False\n",
    "            i+=len(p)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:\n",
    "        index = dict()\n",
    "        for i, tmp in enumerate(pieces):\n",
    "            index[tmp[0]] = i\n",
    "        i = 0\n",
    "        while i < len(arr):\n",
    "            if arr[i] not in index:\n",
    "                return False\n",
    "            tmp = pieces[index[arr[i]]]\n",
    "            if arr[i:i+len(tmp)] != tmp:\n",
    "                return False\n",
    "            i += len(tmp)\n",
    "        return True\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
